package airthmetic.exercise.dp;

public class _10_正则表达式匹配 {
    public boolean isMatch(String s, String p) {
        /**
         * 问题具备重叠子问题和无后效性及最优子结构。动态规划！
         * 什么是原问题？ 什么是子问题？
         * 原问题: s与p 匹配
         * 子问题: s-1 p-1 是否匹配
         *
         * 1.确定状态参数和选择
         * 状态参数是在原问题与子问题之间不断变化并趋近于原问题的值
         *
         * 状态参数：s的第i个字符与p的第j个字符是否匹配
         * 选择/决策： 不断选择i 和 j
         *
         * 2.定义dp table的含义
         * boolean[][] dp = new boolean[m+1][n+1];
         * dp[m][n] 表示 s的前m个字符与p的前n个字符是否匹配
         *
         *
         * 3.初始化dp table
         * 空串与空串是匹配的 所以dp[0][0] = true
         * s不为空串,p为空串的情况下是不能匹配的 所以都是false
         * p不为空串，s为空串的情况下是可能匹配的因为 ‘x’*表示可以有x 0到n个,所以是否匹配要看出现 * 的时候，上上位置上是否匹配
         *
         * dp[0][0] = true;
         *
         * for(int k=0; k<pp.length; k++){
         * if(pp[k] == '*' && dp[0][k-1]){
         * dp[0][k+1] = true;
         * }
         * }
         *
         * 4.推导状态转移公式
         * 根据已知的子问题推导原问题的解
         *
         for(int i=1; i<=m; i++){
         for(int j=1; j<=n; j++){
         // 第一种情况 ss[i] == pp[j] 或者 pp[j] == '.'
         if(ss[i] == pp[j] || pp[j] == '.'){
         dp[i][j] = dp[i-1][j-1];
         }else{
         // 第二种情况
         if(ss[i] != pp[j] && pp[j] != '*'){
         dp[i][j] = false;
         }else if(pp[j] == '*'){
         // 匹配0个或者匹配多个
         dp[i][j] = dp[i-1][j] || dp[i][j-2];
         }
         }
         }
         }
         *
         *
         *
         */

        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        int m = ss.length;
        int n = pp.length;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int k = 0; k < pp.length; k++) {
            if (pp[k] == '*' && dp[0][k - 1]) {
                dp[0][k + 1] = true;
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 第一种情况 ss[i] == pp[j] 或者 pp[j] == '.'
                if (ss[i - 1] == pp[j - 1] || pp[j - 1] == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 第二种情况
                    if (ss[i - 1] != pp[j - 1] && pp[j - 1] != '*') {
                        dp[i][j] = false;
                    } else if (pp[j - 1] == '*') {
                        // 匹配0个或者匹配多个
                        if (pp[j - 1 - 1] == ss[i - 1] || pp[j - 1 - 1] == '.') {
                            dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                        } else {
                            dp[i][j] = dp[i][j - 2];
                        }

                    }
                }
            }
        }

        return dp[m][n];
    }
}
